package com.practice.niuke.new_direct_practice.class23;

/**
 * 汉诺塔游戏的要求把所有的圆盘从左边都移到右边的柱子上， 给定一个整型数组arr，
 * 其中只含有1、 2和3， 代表所有圆盘目前的状态， 1代表左柱， 2代表中柱， 3代表右柱，
 * arr[i]的值代表第i+1个圆盘的位置。 比如， arr=[3,3,2,1]， 代表第1个圆盘在右柱上、
 * 第2个圆盘在右柱上、 第3个圆盘在中 柱上、 第4个圆盘在左柱上 如果arr代表的状态是
 * 最优移动轨迹过程中出现的状态， 返回arr这种状态是最优移动轨 迹中的第几个状态;如
 * 果arr代表的状态不是最优移动轨迹过程中出现的状态， 则返回- 1。
 */
public class Code04_HanoiProblem {

	/**
	 * 调用递归函数的主函数（TODO：标记主函数）
	 *
	 * @param arr
	 * @return
	 */
	public static int step1(int[] arr) {
		if (arr == null || arr.length == 0) {
			return -1;
		}
		return process(arr, arr.length - 1, 1, 2, 3);
	}

	/**
	 * 递归函数，函数的意义（目标是）：把0~i的圆盘，从from全部挪到to上
	 * 返回，根据arr中的状态arr[0..i]，它是最优解的第几步？
	 *
	 * @param arr
	 * @param i
	 * @param from
	 * @param other
	 * @param to
	 * @return
	 */
	public static int process(int[] arr, int i, int from, int other, int to) {
		if (i == -1) {
			// i == -1代表没有圆盘了，直接返回0
			return 0;
		}
		if (arr[i] != from && arr[i] != to) {
			// arr[i]既不在from上也不在to上，一定不可能是最优解中的某一步，返回-1
			return -1;
		}
		if (arr[i] == from) {
			// arr[i]在from上，说明第一大步还没有走完
			return process(arr, i - 1, from, to, other);
		} else { // arr[i] == to
			// 已经走完1， 2两步了
			int rest = process(arr, i - 1, other, from, to); // 第三大步完成的程度
			if (rest == -1) {
				// 第3步违规，说明整体上不是最优解上的某一步，返回-1
				return -1;
			}
			return (1 << i) + rest;
		}
	}

	/**
	 * 使用迭代优化上面的递归过程
	 *
	 * @param arr
	 * @return
	 */
	public static int step2(int[] arr) {
		if (arr == null || arr.length == 0) {
			return -1;
		}
		int from = 1;
		int mid = 2;
		int to = 3;
		int i = arr.length - 1;
		int res = 0;
		int tmp = 0;
		while (i >= 0) {
			if (arr[i] != from && arr[i] != to) {
				return -1;
			}
			if (arr[i] == to) {
				res += 1 << i;
				tmp = from;
				from = mid;
			} else {
				tmp = to;
				to = mid;
			}
			mid = tmp;
			i--;
		}
		return res;
	}

	public static void main(String[] args) {

		int[] arr = { 3, 3, 2, 1 };
		System.out.println(step1(arr));
		System.out.println(step2(arr));

	}
}
